package com.vinjune.algorithm.algorithms;

/**
 * @author 作者：zhangwenjun
 * @version 创建时间：2015年12月9日 下午5:11:01 类说明
 * 
 *  堆是一种重要的数据结构，为一棵完全二叉树, 底层如果用数组存储数据的话，假设某个元素为序号为i(Java数组从0开始,i为0到n-1),
 *  如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。
 *  分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序，
 *  我们使用的是最大堆。处理的思想和冒泡排序，选择排序非常的类似，一层层封顶，只是最大元素的选取使用了最大堆。
 *  最大堆的最大元素一定在第0位置，构建好堆之后，交换0位置元素与顶即可。堆排序为原位排序(空间小), 且最坏运行时间是O(n2)，是渐进最优的比较排序算法。
 *  
 */

public class Heapsort {

	// public static void main(String[] args) {
	// int[] h = new int[] {49,38,65,97,76,13,27,49}; //下标从0开始
	//
	// heapSort(h);
	//
	// for(int i=0;i<h.length;i++)
	// System.out.print(h[i] + " ");
	// }
	//
	// public static void heapSort(int[] h) { //堆采用数组存储表示
	// //对数组h进行堆排序
	// for(int i=h.length/2-1;i>=0;i--) //把h[0..h.length-1]建成大根堆
	// heapAdjust(h, i, h.length-1);
	// for(int j=h.length-1;j>=0;j--) {
	// int temp = 0; //辅助空间
	// temp = h[0];
	// h[0] = h[j]; // 将堆顶元素和当前未经排序子序列h[0..j]中的最后一个记录交换
	// h[j] = temp;
	//
	// heapAdjust(h, 0, j-1); //将h[0..j-1]调整为大根堆
	// }
	// }
	//
	// private static void heapAdjust(int[] h, int s, int m) {
	// //h[s..m]为需要调整的元素范围
	// //h[s-1..m]满足堆的定义，现在需要调整h[s]使h[s..m]成为一个大根堆
	// int temp = 0;
	// temp = h[s];
	// for(int i=2*s;i<=m;i*=2) {
	// if(i<m && h[i]<h[i+1]) //i应该为值较大的记录的下标
	// i++;
	// if(temp>=h[i]) //temp应该插入在位置s上
	// break;
	// h[s] = h[i];
	// s = i ;
	// }
	// h[s] = temp; //插入在此位置
	// }

	public static void main(String[] args) {
		int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };

		System.out.println("Before heap:");
		ArrayUtils.printArray(array);

		heapSort(array);

		System.out.println("After heap sort:");
		ArrayUtils.printArray(array);
	}

	public static void heapSort(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}

		buildMaxHeap(array);

		for (int i = array.length - 1; i >= 1; i--) {
			ArrayUtils.exchangeElements(array, 0, i);

			maxHeap(array, i, 0);
		}
	}

	private static void buildMaxHeap(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}

		int half = array.length / 2;
		for (int i = half; i >= 0; i--) {
			maxHeap(array, array.length, i);
		}
	}

	private static void maxHeap(int[] array, int heapSize, int index) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;

		int largest = index;
		if (left < heapSize && array[left] > array[index]) {
			largest = left;
		}

		if (right < heapSize && array[right] > array[largest]) {
			largest = right;
		}

		if (index != largest) {
			ArrayUtils.exchangeElements(array, index, largest);

			maxHeap(array, heapSize, largest);
		}
	}

}
